home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_05 / 1105048a < prev    next >
Text File  |  1993-03-02  |  2KB  |  83 lines
  1. #include "btree.h"
  2.  
  3. #undef VERBOSE
  4.  
  5. #ifdef __TURBOC__
  6. extern unsigned int _stklen = 24576;
  7. #endif
  8.  
  9. const int NumInts = 1000;
  10. const int NumReps = 1000;
  11.  
  12. int
  13. compare_ints(const void *a, const void *b)
  14. {
  15.     return *(const int *) a - *(const int *) b;
  16. }
  17.  
  18. int
  19. main()
  20. {
  21.     int *arr = new int[NumInts];
  22.     int seed;
  23.     BinaryTree<int> *inttree;
  24.  
  25.     randomize();
  26.  
  27.     for (int i = 0; i < NumReps; i++) {
  28.     int j;
  29.     int min = INT_MAX;
  30.     int max = INT_MIN;
  31.  
  32.     inttree = new BinaryTree<int>;
  33.  
  34.     cout << i << '\n';
  35.  
  36.     for (j = 0; j < NumInts; j++) {
  37.         int x = rand();
  38.         if (x < min)
  39.         min = x;
  40.         if (x > max)
  41.         max = x;
  42.         arr[j] = x;
  43.             inttree->Insert(x);
  44.         if (inttree->CheckInvariant())
  45.         cout << "Problems\n";
  46.     }
  47.     if (min != *inttree->Min() ||
  48.         max != *inttree->Max())
  49.         cout << "Min/max problems\n";
  50.     for (j = 0; j < NumInts; j++) {
  51.         BinaryTreeIter<int> q(*inttree, arr[j]);
  52.         if (*q.Contents() != arr[j])
  53.         cout << "Serious problem\n";
  54.     }
  55.     BinaryTreeIter<int> *inorder = new BinaryTreeIter<int>(*inttree);
  56.     inorder->Min();
  57.     if (min != *inorder->Contents())
  58.         cout << "Problems in inorder initialization\n";
  59.     j = 0;
  60.     qsort(arr, NumInts, sizeof(int), compare_ints);
  61.     while (inorder->Contents()) {
  62.         inorder->Succ();
  63.         int *next = inorder->Contents();
  64.         if (next && (*next < min || *next != arr[++j]))
  65.         cout << "Problems in inorder traversal\n";
  66.         if (next)
  67.             min = *next;
  68.     }
  69.     for (j = 0; j < NumInts; j++) {
  70.         inttree->DeleteItem(arr[j]);
  71.         if (inttree->CheckInvariant())
  72.         cout << "Problems deleting\n";
  73.         BinaryTreeIter<int> q(*inttree, arr[j]);
  74.         if (q.Contents() && arr[j+1] != arr[j])
  75.         cout << "Problems deleting II\n";
  76.     }
  77.     delete inttree;
  78.     }
  79.     return 0;
  80. }
  81.  
  82.  
  83.